package leetcode.tencent;

/**
 * @author Cheng Jun
 * Description: 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数
 * @version 1.0
 * @date 2021/11/6 10:48
 * 面试题 二刷 困难题
 */
public class findMedianSortedArrays {

    public static void main(String[] args) {
        System.out.println(findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4}));
    }
    // 暴力解法，System.arraycopy 然后 Arrays.sort，时间复杂度 O( (m+n)log(m+n) )

    // 双指针 找到中间（两个数组变为一个数组）的两个数字或一个数字
    static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        int midIndex = (length1 + length2) / 2;
        int[] arr = new int[length1 + length2];
        // 1 2 3 4 5 6
        // 1 2 3 4 5
        // 中位数的左右下标
        int left;
        int right;
        if (((length1 + length2) & 1) == 1) {
            left = midIndex;
        } else {
            left = midIndex - 1;
        }
        right = midIndex;
        int i = 0;
        int j = 0;
        int arri = 0;
        while (i < length1 && j < length2) {
            if (nums1[i] < nums2[j]) arr[arri++] = nums1[i++];
            else arr[arri++] = nums2[j++];
        }
        // 数组元素 找够了
        while (i < length1 && arri <= right) arr[arri++] = nums1[i++];
        while (j < length2 && arri <= right) arr[arri++] = nums2[j++];

        return (arr[left] + arr[right]) / 2.0;
    }

    // todo 还有更好的二分查找法，有空再学习
    // https://leetcode.cn/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
}
